1. Field of the Invention
Methods and apparatus consistent with the present invention relate to performing address mapping in a virtual file system of a storage unit having a plurality of non-volatile data storage media, and more particularly, to reducing a metadata processing time associated with address mapping performed in a virtual file system, so as to input/output burst data at a high speed.
2. Description of the Related Art
In general, multimedia devices such as mobile devices store and provide large-size multimedia data such as MP3 music and video to users. A storage unit used in the multimedia devices provides a large-capacity storage space, and is one in which data can be read from and written to at a high speed.
A flash memory, which is a non-volatile data storage unit, has been widely used as the storage unit of mobile devices due to its low power, miniaturization, low heat generation, high stability, and the like. In addition, as the density of the flash memory has rapidly increased and the demand by users for a large capacity memory increases, a capacity that can be stored in a single memory has rapidly increased.
FIG. 1 is a function block diagram for explaining a related art address mapping method used in a single flash memory chip.
A host device 110 transmits a logical address in units of 512 bytes to a flash memory device 120 to request the flash memory device 120 to input/output data. Since a data structure of a file system used by the host device 110 and a data structure used by the flash memory device 120 to read and write data are different from each other, the flash memory device 120 includes a flash translation layer (FTL) 121 as a virtual file system to translate the logical address transmitted from the host device 110 to a physical address, which is an address used to practically read and write data. After the logical address is mapped to the physical address by the FTL 121, map table data and user data 123-3 may be written to or read from a flash memory 123 through a memory controller 122. The map table includes the block map table 123-1, for mapping data in units of blocks, and the page map table 123-2, for mapping data in units of 64 pages in each block. In general, the block map table 123-1 is stored in a metadata block in the flash memory 123, and the page map table 123-2 is stored in a spare area in a user data block.
The address mapping operation of translating the logical address to the physical address in order to write and erase data to and from the storage unit as illustrated in FIG. 1 is applied to non-volatile data storage units in addition to the flash memory 123, so that a description provided later is also applicable to non-volatile data storage units.
FIG. 2 is a view illustrating an N-channel/4-way hardware architecture using a flash memory, according to related art.
Generally a flash memory has a slow write speed. Therefore, in order for the memory controller to perform high-speed data input/output and not waste time waiting in a standby mode, various hardware architectures included in the flash memory storage unit have been proposed.
Referring to FIG. 2, a flash memory controller 210 and 4 flash memories per channel are illustrated. A general flash memory storage unit uses a number of flash memory chips as illustrated in order to increase a storage capacity and improve a data input/output performance. In a first channel 220, 4 flash memories 221 to 224 are connected via a system bus to apply interleaving in order to minimize a wait time of the flash memory controller 210 when a write operation, that is, programming is performed on the flash memories 221 to 224.
The write operation performed on the flash memory includes: i) loading data to be written into a page buffer included in the flash memory; and ii) writing the data loaded into the page buffer in a cell array of the flash memory. In order to perform the two steps at a high speed, the general flash memory storage unit connects a number of the flash memory chips in a single channel in order for the memory chips to be controlled by the flash memory controller 210 to input/output data in an interleaving technique. According to a general flash memory standard, when a single channel uses 4 or 5 flash memory chips, further performance improvement cannot be expected. Therefore, the 4-way architecture in which address distribution can be easily performed to the exponent of 2 is mainly used.
The read and the write operations are performed on the flash memory generally in units of pages, and an erase operation is performed in units of blocks including a number of pages in order to perform the write operation again for updating. This characteristic is different from that of a general storage unit, and for compatibility with an existing file system, the aforementioned FTL 121, which is software (virtual file system), is used to manage the general flash memory storage unit and provide compatibility with the existing file system. The virtual file system, for the compatibility with the file system, can be applied to other non-volatile data storage units.
Due to technical development, the data input/output processing speed of a large-capacity flash memory storage unit is increased to a substantially theoretical maximum speed in hardware. However, an algorithm for faster data input/output processing in terms of software is still required.
Specifically, in the aforementioned hardware architecture structure, the FTL 121 transmits various commands to each flash memory in response to a read/write request from the file system. When it is assumed that a storage unit using a single flash memory chip is used as illustrated in FIG. 1, commands transmitted from the FTL 121 to the hardware in response to the data write request of the host device 110 include metadata commands such as map table read/update, block erase, block merge, and the like and data commands for inputting/outputting practically requested user data. The FTL operations are associated with address mapping for translating a logical address to a physical address in order to read, write, and erase user data.
When the above-mentioned method is applied to a flash memory storage unit using a number of chips for high-speed data input/output as illustrated in FIG. 2, a plurality of pieces of independent metadata exist in units of flash memory chip devices or channels. Therefore, in this structure, based on the data input/output request of the file system, the FTL 121 transmits a different command to each of the metadata. Accordingly, each of the independent FTL metadata has a different metadata command set and therefore has a different execution time.
As the units of the commands managed by the FTL 121 increase, complexity associated with the address mapping in the FTL 121 increases. Due to the increase in the complexity of the FTL 121, a code size of the FTL 121 also increases, memory usage increases, and a processing time of the CPU increases. Consequently, resource usage increases. The increase in the throughput of the FTL 121 results in occurrence of a delay time for each command issue. In addition, the user data input/output commands are concentrated at a specific point in time, so that burst data transmission between the host and the storage unit cannot be easily performed, and this may degrade a performance improvement effect caused by interleaving. Accordingly, a part for processing the address mapping of the FTL 121 in the entire system may function as a bottleneck. Therefore, a new algorithm, in terms of software, for decreasing a time to process the address mapping is required.